// https://leetcode.cn/problems/longest-common-subsequence/description/

// 算法思路总结：
// 1. 使用动态规划求解最长公共子序列
// 2. dp[i][j]表示text1前i个字符和text2前j个字符的LCS长度
// 3. 字符相等时长度等于左上角值加1
// 4. 字符不等时取上方和左方的最大值
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm> 

class Solution 
{
public:
    int longestCommonSubsequence(string text1, string text2) 
    {
        int m = text1.size(), n = text2.size();
        text1 = " " + text1;
        text2 = " " + text2;

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 1 ; j <= n ; j++)
            {
                if (text1[i] == text2[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
};

int main()
{
    string s11 = "abcde", s12 = "ace";
    string s21 = "abc", s22 = "abc";
    Solution sol;

    cout << sol.longestCommonSubsequence(s11, s12) << endl;
    cout << sol.longestCommonSubsequence(s21, s22) << endl;

    return 0;
}